IMPLEMENTATION MODULE Tad_ArbolBinario;

FROM StrIO IMPORT WriteString, WriteLn,WriteString;  
FROM FIO IMPORT OpenToRead,Close,File,Exists,ReadString;
FROM DynamicStrings IMPORT String, ConCat, InitString, CopyOut, char;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;
FROM NumberIO IMPORT ReadInt,WriteInt;
FROM DynamicStrings IMPORT String, Slice, CopyOut, Index, InitString;
FROM StringConvert IMPORT StringToInteger;
FROM FpuIO IMPORT WriteReal;
FROM SYSTEM IMPORT ADDRESS;
IMPORT Tad_Lista;

  TYPE Arbol = POINTER TO RECORD 
        raiz : POINTER TO Nodo;
        fin : POINTER TO Nodo;
        tamanio : INTEGER;
        END;
        
  Nodo = RECORD
        info : ADDRESS;
        valor : REAL;
        ant,sig : POINTER TO Nodo;
        END;

  PROCEDURE CrearArbol() : Arbol;
  VAR a : Arbol;

  BEGIN
        NEW(a);
        IF (a = NIL) THEN
                 RETURN a;
        END;

        a^.raiz := NIL;
        a^.fin := NIL;
        a^.tamanio := 0;
        RETURN a;
   END CrearArbol;

  PROCEDURE Arbol_esVacio(a : Arbol) : BOOLEAN;
  BEGIN
     RETURN a^.raiz = NIL;
  END Arbol_esVacio;

  PROCEDURE Agregar (VAR a : Arbol; nuevo : ADDRESS; valor : REAL);
  VAR aux               : POINTER TO Nodo;
  VAR i,j               : INTEGER;
  BEGIN
        NEW(aux);
        IF (nuevo = NIL) OR (aux = NIL) THEN
		RETURN;
	END;
	
        aux^.info := nuevo;
        aux^.valor := valor;
        aux^.sig := NIL;
        aux^.ant := NIL;

	IF (a^.tamanio = 0) THEN
                a^.raiz := aux;
                a^.tamanio := 1;
                a^.fin := aux;
                RETURN;
        ELSE
                a^.fin^.sig := aux;
                aux^.ant := a^.fin;
                a^.fin := aux;
                a^.tamanio := a^.tamanio + 1;
        
                i := a^.tamanio;

                j := i DIV 2;

                WHILE (Obtener_Valor(a,j) < valor) AND (j <> 0) DO
                        Intercambiar(a,j,i);
                        i := i DIV 2;
                        j := i DIV 2;
                END;
                        
        END;        

END Agregar;

  PROCEDURE Intercambiar (a : Arbol; pos1 :INTEGER; pos2 : INTEGER);
  VAR aux1,aux2,nav : POINTER TO Nodo;
  VAR i,valor       : INTEGER;
  VAR esta1,esta2   : BOOLEAN;
  VAR info          : ADDRESS;
  BEGIN
        IF a = NIL THEN
                RETURN;
        END;
        
        i := 1;

        nav := a^.raiz;
        
        WHILE NOT(esta1 AND esta2) AND (i <= a^.tamanio) DO
                IF (i = pos1) THEN
                        aux1 := nav;
                        esta1 := TRUE;
                ELSIF (i = pos2) THEN
                        aux2 := nav;
                        esta2 := TRUE;
                END;
                
                nav := nav^.sig;
                i := i + 1;
        END;

        valor := aux1^.valor;
        info := aux1^.info;
        aux1^.valor := aux2^.valor;
        aux1^.info := aux2^.info;
        aux2^.valor:= valor;
        aux2^.info := info;
        
  END Intercambiar;

  PROCEDURE Obtener_Valor ( a : Arbol; pos : INTEGER) : REAL;
  VAR nav  : POINTER TO Nodo;
  VAR i    : INTEGER;
  VAR valor: REAL;
  BEGIN
        IF a = NIL THEN
                RETURN -1.0;
        END;

        IF pos > a^.tamanio THEN
                RETURN -1.0;
        END;

        i := 1;
        nav := a^.raiz;
        WHILE i <= pos DO
                IF i = pos THEN
                        valor := nav^.valor;
                END;
        nav := nav^.sig;
        i := i + 1;
        END;

        RETURN valor;
  END Obtener_Valor;

  PROCEDURE GetMaximo (VAR a : Arbol) : ADDRESS;
  VAR max : ADDRESS;
  VAR i       : INTEGER;
  BEGIN

        IF a = NIL THEN
                RETURN NIL;
        END;                

        IF a^.raiz = NIL THEN
                RETURN NIL;
        END;

        max := a^.raiz^.info;

        IF a^.tamanio = 1 THEN
                a^.tamanio := 0;
                a^.raiz := NIL;
                a^.fin := NIL;
                RETURN max;
        END;

        Intercambiar(a,1,a^.tamanio);
        a^.tamanio := a^.tamanio - 1;
        
        i := 1;
        WHILE (Obtener_Valor(a,i) < Obtener_Valor(a,(2*i))) OR (Obtener_Valor(a,i) < Obtener_Valor(a,(2*i + 1))) DO
                IF Obtener_Valor(a,(2*i)) < Obtener_Valor(a,(2*i + 1)) THEN
                        Intercambiar(a,i,(2*i + 1));
                        i := 2*i + 1;
                ELSE
                        Intercambiar(a,i,(2*i));
                        i := 2*i;
                END;
        END;

        RETURN max;
END GetMaximo;

  PROCEDURE ListaOrdenada (VAR a : Arbol; function : funImprimir ): Tad_Lista.Lista;
  VAR l : Tad_Lista.Lista;
  VAR elem : ADDRESS;
  VAR valido : BOOLEAN;
  BEGIN
        l := Tad_Lista.Crear_Lista(function);
        WHILE a^.tamanio <> 0 DO
                elem := GetMaximo(a);
                valido := Tad_Lista.Lista_Agregar(l,elem);
        END;
        
        RETURN l;
END ListaOrdenada;
  
  PROCEDURE Clonar (a : Arbol) : Arbol;
  VAR clon : Arbol;
  VAR nav : POINTER TO Nodo;
  BEGIN
        clon := CrearArbol();
        nav := a^.raiz;
        WHILE nav <> NIL DO
                Agregar(clon,nav^.info,nav^.valor);
                nav := nav^.sig;
        END;

        RETURN clon;
END Clonar;

END Tad_ArbolBinario.
